package com.example.demo;

import java.util.HashMap;

class LRUCache {

    class Node{
        Node next;
        Node pre;
        int value;
        int key;
        Node(int k,int v){
            next = this;
            pre = this;
            key = k;
            value= v;
        }
    }
    HashMap<Integer,Node> map = new HashMap<>();
    int capacity;
    Node head;
    public LRUCache(int capacity) {

        this.capacity = capacity;
        head = new Node(-1,-1);

//        this.capacity = capacity;
//        head = new Node(-1,-1);
    }
    
    public int get(int key) {
        if(map.containsKey(key)){
            Node node = map.get(key);
            refresh(node);
            return node.key;
        }else {
            return -1;
        }
//        if(!map.containsKey(key)) return -1;
//        Node node = map.get(key);
//        refresh(node);
//        return node.value;
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)){
            Node node = map.get(key);
            node.value = value;
            refresh(node);
        }else {
            Node node = new Node(key,value);
            map.put(key,node);
            refresh(node);
            if(map.size()>capacity){
                del();
            }
        }
//        if(map.containsKey(key)){
//            Node node = map.get(key);
//            node.value = value;
//            refresh(node);
//        }else{
//            Node node = new Node(key,value);
//            map.put(key,node);
//            refresh(node);
//            if(map.size()> capacity){
//                del();
//            }
//        }
    }
    //1  node 2
    // 1 ->2->  3  1 node 2 
     //  1<-2<-3
    private void refresh(Node node){

        node.next.pre = node.pre;
        node.pre.next = node.next;

       node.next =  head.next ;
       node.pre = head;
       head.next.pre = node;
       head.next = node;
//        //qudiao
//        node.next.pre = node.pre;
//        node.pre.next = node.next;
//
//        //插入head之后
//        node.next = head.next;
//        node.pre = head;
//        head.next.pre = node;
//        head.next = node;
        
    }

    private void del(){
        Node node = head.pre;
        node.next.pre = node.pre;
        node.pre.next = node.next;
        map.remove(node.key);



//        Node node = head.pre;
//        node.next.pre=node.pre;
//        node.pre.next = node.next;
//        map.remove(node.key);
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */